package leetcode;

import java.io.PrintStream;

public class LeetCode147 {

    public ListNode insertionSortList1(ListNode head) {

        //p当前指针
        ListNode result = head, p = head.next;
        while (p != null) {
            ListNode node = p;
            ListNode next = p.next;
            if (node.val < result.val) {
                node.next = result;
                result = node;
            } else {

            }
        }
        return result;
    }

    // next value不使用当前value
    public ListNode insertionSortList(ListNode head) {
        ListNode newHead = new ListNode(Integer.MIN_VALUE), newTail = newHead;
        ListNode node = head, next, p, pre;
        int max = Integer.MIN_VALUE;
        while (node != null) {
            next = node.next;
            if (node.val >= max) {
                newTail.next = node;
                max = node.val;
                newTail = node;
                node.next = null;
            } else {
                p = newHead;
                pre = newHead;
                while (p != null) {
                    if (node.val < p.val) {
                        node.next = pre.next;
                        pre.next = node;
                        break;
                    }
                    pre = p;
                    p = p.next;
                }
            }
            node = next;
        }
        return newHead.next;
    }
//------------------------------------------------------------------
}
